using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;

namespace GeoAzure.Core
{
    public class OverflowAlgorithm<T> : IOverflowAlgorithm<T>
        where T : class 
    {
        public const int MaxObjectsPerNode = 10;
        public const int MinObjectsPerNode = 4; // 40% of Max

        TreeNode<T> IOverflowAlgorithm<T>.HandleNodeOverflow(TreeNode<T> targetNode, InsertionContext<T> context)
        {
            if (targetNode.Entries.Count > MaxObjectsPerNode)  // the node actually overflows
            {
                //if (!targetNode.IsRoot && !context.HasLevelOverflownPreviously(targetNode.Level))
                //{
                //    context.AddOverflownLevel(targetNode.Level);
                //    Reinsert(targetNode, context);
                //    return false;
                //}
                //else
                {
                    return Split(targetNode, context);
                }
            }
            return null;
        }
        /// <summary>
        /// 
        /// </summary>
        /// <param name="treeNode"></param>
        /// <param name="context"></param>
        /// <returns>true if the node is underfilled and scheduled for deletion, false otherwise.</returns>
        public bool HandleNodeUnderflow(TreeNode<T> treeNode, DeletionContext<T> context)
        {
            bool isRoot = treeNode.IsRoot;
            if ((isRoot && treeNode.Entries.Count == 1 && !treeNode.IsLeaf) || (!isRoot && treeNode.Entries.Count < MinObjectsPerNode))
            {
                // we have to eliminate the node, as it is underfilled
                // collect it to redistribute its entries later
                // the exception is when we delete the root node: its single entry left does not need
                // to be reinserted, as it will become the new root
                if (!isRoot)
                    context.AddDeletedNode(treeNode);
                // and delete it from its parent
                // TODO: rewrite the code hereunder
                //bool wasNodeRemoved = treeNode.Parent.Delete(new DeletionContext<T>(treeNode, treeNode.Level + 1, context));
                //Debug.Assert(wasNodeRemoved);
                return true;
            }
            return false;
        }

/*
        private void Reinsert(TreeNode<T> targetNode, InsertionContext<T> context)
        {
            // sort the entries by their distance to the center of enclosing bounding rect, decreasing
            var entries = targetNode.Entries;
            var nodeBoundsCenter = targetNode.Bounds.Center;
            entries.Sort((n1, n2) => Math.Sign(n2.Bounds.Center.DistanceTo(nodeBoundsCenter) -
                                                           n1.Bounds.Center.DistanceTo(nodeBoundsCenter)));

            const int itemsToRemove = (int) (MaxObjectsPerNode * 0.3);

            var removedEntries = new IndexEntry<T>[itemsToRemove];

            // now remove entries from target node, and collect them
            int removedItemsCount = 0;
            for (int i = 0; i < entries.Count && i < itemsToRemove; i++)
            {
                removedEntries[i] = entries[0];
                entries.RemoveAt(0);
                removedItemsCount++;
            }

            // recompute the minimum bounding rectangle of the target node, without the removed entries
            GeoRectangle newBounds = GeoRectangle.CreateMinimumBoundingRectangle(entries);

            targetNode.Bounds = newBounds;

            // now do the actual reinsertion
            // notice that items to be reinserted are still sorted by decreasing distance to the previous
            // center of the target node
            // as a close reinsert outperforms a far reinsert,
            // we will reinsert items starting with the last item removed
            // and go backwards
            for (int j = removedItemsCount - 1; j >= 0; j--)
            {
                // TODO: we have to reinsert in the root of the index, not in the node's parent
                targetNode.Parent.Insert(new InsertionContext<T>(removedEntries[j], targetNode.Level, context));
            }

        }
*/

        private TreeNode<T> Split(TreeNode<T> targetNode, InsertionContext<T> context)
        {
            GeoRectangle newNodeBounds;
            GeoRectangle updatedBounds;
            List<IndexEntry<T>> newNodeEntryList;
            // TODO: possible optimization by avoiding recalculation of bounds later
            Split(targetNode.Entries, out updatedBounds, out newNodeEntryList, out newNodeBounds);
            return targetNode.SplitNode(newNodeEntryList, newNodeBounds, updatedBounds, context);
        }

        private void Split(List<IndexEntry<T>> nodeEntries, out GeoRectangle updatedInputBounds, out List<IndexEntry<T>> secondElementList, out GeoRectangle secondBounds)
        {
            Distribution[] upperDistributions, lowerDistributions;
            ChooseSplitAxis(nodeEntries, out upperDistributions, out lowerDistributions);
            Distribution chosen = ChooseSplitIndex(upperDistributions, lowerDistributions);
            updatedInputBounds = chosen.FirstGroupBoundingBox;
            secondBounds = chosen.SecondGroupBoundingBox;
            secondElementList = DistributeEntries(nodeEntries, chosen);
        }

        private void ChooseSplitAxis(IList<IndexEntry<T>> nodeEntries, out Distribution[] upperDistributions, out Distribution[] lowerDistributions)
        {
            // first sort the entries by their top latitude values, descending
            // this will "group" entries having their tops close to each other
            var topLatitudeSort = nodeEntries.OrderByDescending(e => e.Bounds.TopLeft.Latitude).ToArray();
            // then do the same will latitude bottom values, ascending
            var bottomLatitudeSort = nodeEntries.OrderBy(e => e.Bounds.BottomRight.Latitude).ToArray();
            // follow with longitude
            var rightLongitudeSort =
                nodeEntries.OrderByDescending(e => e.Bounds.TopRight.Longitude).ToArray();
            var leftLongitudeSort =
                nodeEntries.OrderBy(e => e.Bounds.BottomLeft.Longitude).ToArray();
            // calculate the entry distributions
            const int numberOfDistributions = MaxObjectsPerNode - 2 * MinObjectsPerNode + 2;

            Distribution[] topLatitudeDistributions = new Distribution[numberOfDistributions];
            Distribution[] bottomLatitudeDistributions = new Distribution[numberOfDistributions];
            Distribution[] rightLongitudeDistributions = new Distribution[numberOfDistributions];
            Distribution[] leftLongitudeDistributions = new Distribution[numberOfDistributions];

            double sumOfLatitudeMargins = 0d, sumOfLongitudeMargins = 0d;
            for (int k = 1; k <= numberOfDistributions; k++)
            {
                topLatitudeDistributions[k - 1] = CalculateDistribution(k, topLatitudeSort);
                sumOfLatitudeMargins += topLatitudeDistributions[k - 1].MarginValue;

                bottomLatitudeDistributions[k - 1] = CalculateDistribution(k, bottomLatitudeSort);
                sumOfLatitudeMargins += bottomLatitudeDistributions[k - 1].MarginValue;

                rightLongitudeDistributions[k - 1] = CalculateDistribution(k, rightLongitudeSort);
                sumOfLongitudeMargins += rightLongitudeDistributions[k - 1].MarginValue;

                leftLongitudeDistributions[k - 1] = CalculateDistribution(k, leftLongitudeSort);
                sumOfLongitudeMargins += leftLongitudeDistributions[k - 1].MarginValue;
            }
            if (sumOfLatitudeMargins < sumOfLongitudeMargins)
            {
                upperDistributions = topLatitudeDistributions;
                lowerDistributions = bottomLatitudeDistributions;
            }
            else
            {
                upperDistributions = rightLongitudeDistributions;
                lowerDistributions = leftLongitudeDistributions;
            }
        }

        private Distribution ChooseSplitIndex(Distribution[] upperDistributions, Distribution[] lowerDistributions)
        {
            double chosenOverlap = double.MaxValue;
            double chosenAreaValue = double.MaxValue;
            Distribution chosen = null;
            for (int j = 0; j < 2; j++)
            {
                Distribution[] distributions = j == 0 ? upperDistributions : lowerDistributions;
                for (int i = 0; i < distributions.Length; i++)
                {
                    Distribution current = distributions[i];
                    GeoRectangle? intersectionOfGroups =
                        current.FirstGroupBoundingBox.IntersectionWith(current.SecondGroupBoundingBox);
                    double overlapArea = intersectionOfGroups.HasValue ? intersectionOfGroups.Value.Area : 0d;

                    if (overlapArea < chosenOverlap ||
                        (overlapArea == chosenOverlap && current.AreaValue < chosenAreaValue))
                    {
                        chosen = current;
                        chosenAreaValue = current.AreaValue;
                        chosenOverlap = overlapArea;
                    }
                }
            }
            return chosen;
        }

        internal Distribution CalculateDistribution(int distributionIndex, IndexEntry<T>[] sortedEntries)
        {
            // Check we have a number of entries corresponding to the split limit
            Debug.Assert(sortedEntries.Length == MaxObjectsPerNode + 1);
            Debug.Assert(distributionIndex >= 1);

            var result = new Distribution();
            int firstGroupNumberOfEntries = MinObjectsPerNode - 1 + distributionIndex;

            result.FirstGroup = new IndexEntry<T>[firstGroupNumberOfEntries];
            result.FirstGroupBoundingBox = sortedEntries[0].Bounds;
            result.SecondGroup = new IndexEntry<T>[MaxObjectsPerNode + 1 - firstGroupNumberOfEntries];
            result.SecondGroupBoundingBox = sortedEntries[firstGroupNumberOfEntries].Bounds;
            for (int entryIndex = 0; entryIndex < MaxObjectsPerNode + 1; entryIndex++)
            {
                if (entryIndex < firstGroupNumberOfEntries)
                {
                    result.FirstGroup[entryIndex] = sortedEntries[entryIndex];
                }
                else
                {
                    result.SecondGroup[entryIndex - firstGroupNumberOfEntries] = sortedEntries[entryIndex];
                }
            }
            result.FirstGroupBoundingBox = GeoRectangle.CreateMinimumBoundingRectangle(result.FirstGroup);
            result.SecondGroupBoundingBox = GeoRectangle.CreateMinimumBoundingRectangle(result.SecondGroup);
            Debug.Assert(sortedEntries.Length == result.FirstGroup.Length + result.SecondGroup.Length);
            return result;
        }

        private List<IndexEntry<T>> DistributeEntries(List<IndexEntry<T>> nodeEntries, Distribution chosenDistribution)
        {
            var newElementList = new List<IndexEntry<T>>(chosenDistribution.SecondGroup);
            nodeEntries.Clear();
            nodeEntries.AddRange(chosenDistribution.FirstGroup);
            return newElementList;
        }

        internal class Distribution
        {
            public IndexEntry<T>[] FirstGroup;
            public GeoRectangle FirstGroupBoundingBox;
            public IndexEntry<T>[] SecondGroup;
            public GeoRectangle SecondGroupBoundingBox;
            public double AreaValue
            {
                get { return FirstGroupBoundingBox.Area + SecondGroupBoundingBox.Area; }
            }
            public double MarginValue
            {
                get { return FirstGroupBoundingBox.Perimeter + SecondGroupBoundingBox.Perimeter; }
            }
        }


    }

}